// 封装链表的构造函数
function LinkedList() {
  // 封装一个Node类, 用于保存每个节点信息
  function Node(value) {
    this.value = value;
    this.next = null;
  }

  // 链表中的属性 长度和头节点
  this.length = 0;
  this.head = null;

  // 链表尾部追加元素方法
  this.append = function (value) {
    // 1.根据新元素创建节点
    let newNode = new Node(value);

    // 2.判断原来链表是否为空
    if (this.head === null) {
      // 链表尾空
      this.head = newNode;
    } else {
      // 链表不为空
      // 2.1.定义变量, 保存当前找到的节点
      let current = this.head;
      while (current.next) {
        current = current.next;
      }

      // 2.2.找到最后一项, 将其next赋值为node
      current.next = newNode;
    }

    // 3.链表长度增加1
    this.length++;
  };

  // 链表的toString方法
  this.toString = function () {
    // 1.定义两个变量
    let current = this.head;
    let listString = "";

    // 2.循环获取链表中所有的元素
    while (current) {
      listString += "," + current.value;
      current = current.next;
    }

    // 3.返回最终结果
    return listString.slice(1);
  };

  // 根据下标插入元素
  this.insert = function (position, value) {
    // 1.检测越界问题: 越界插入失败
    if (position < 0 || position > this.length) return false;

    // 2.定义变量, 保存信息
    let newNode = new Node(value);
    let current = this.head;
    let previous = null;
    index = 0;

    // 3.判断是否列表是否在第一个位置插入
    if (position == 0) {
      newNode.next = current;
      this.head = newNode;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      newNode.next = current;
      previous.next = newNode;
    }

    // 4.length+1
    this.length++;

    return true;
  };

  // 根据位置移除节点
  this.removeAt = function (position) {
    // 1.检测越界问题: 越界移除失败, 返回null
    if (position < 0 || position >= this.length) return null;

    // 2.定义变量, 保存信息
    let current = this.head;
    let previous = null;
    let index = 0;

    // 3.判断是否是移除第一项
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
    }

    // 4.length-1
    this.length--;

    // 5.返回移除的数据
    return current.value;
  };

  // 根据元素获取链表中的位置
  this.indexOf = function (value) {
    // 1.定义变量, 保存信息
    let current = this.head;
    index = 0;

    // 2.找到元素所在的位置
    while (current) {
      if (current.value === value) {
        return index;
      }
      index++;
      current = current.next;
    }

    // 3.来到这个位置, 说明没有找到, 则返回-1
    return -1;
  };

  // 根据元素删除信息
  this.remove = function (value) {
    let index = this.indexOf(value);
    return this.removeAt(index);
  };

  // 判断链表是否为空
  this.isEmpty = function () {
    return this.length == 0;
  };

  // 获取链表的长度
  this.size = function () {
    return this.length;
  };

  // 获取第一个节点
  this.getFirst = function () {
    return this.head.value;
  };
}

// new出一个链表实例
let head = new LinkedList();
// 给链表中添加元素
head.append(1);
head.append(2);
head.append(3);
head.append(4);
head.append(5);
// 链表中的属性 - 长度
console.log("当前链表的长度是 -", head.length);
// 链表中的属性 - 长度
console.log("当前链表的头节点是 -", head.head);
// 链表的toString方法 转换为字符串
console.log("当前链表转换为字符串是 -", head.toString());
// 链表根据下标插入元素
console.log("链表根据下标插入元素 -", head.insert(2, 999));
// 链表的toString方法 转换为字符串
console.log("insert元素之后链表转换为字符串是 -", head.toString());
// 链表根据元素获取链表中的位置
console.log(
  "根据元素获取链表中的位置,节点999所在的位置是 -",
  head.indexOf(999)
);
// 根据元素删除信息
console.log("根据元素删除信息,删除元素5之后 -", head.remove(5));
// 链表的remove方法 删除节点5之后转为字符串
console.log("链表的remove方法 删除节点5之后转为字符串是 -", head.toString());
// 判断链表是否为空
console.log("判断链表是否为空 -", head.isEmpty());
// 获取链表的长度
console.log("获取链表的长度 -", head.size());
// 获取链表第一个节点
console.log("获取链表第一个节点是 -", head.getFirst());

// --------------------------------------------------------
// --------------------------------------------------------
// ------------------下面是class写法------------------------
// --------------------------------------------------------
// --------------------------------------------------------

// 链表中节点类-ES6
class Node {
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}

// 链表类-ES6
class LinkedListClass {
  constructor() {
    // 初始化要设置链表长度和头节点
    this.length = 0;
    this.head = null;
  }
  // 判断链表是否为空
  IsEmpty() {
    return this.length === 0;
  }
  // 获取链表的长度
  Size() {
    return this.length;
  }
  // 尾部添加节点
  Append(val) {
    // 1.根据新元素创建节点
    const newNode = new Node(val);
    // 2.判断原来链表是否为空
    if (!this.head) {
      // 若是链表为空就让当前节点为头节点
      this.head = newNode;
    } else {
      // 链表不为空
      // 2.1.定义变量, 保存当前找到的节点
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      // 2.2.找到最后一项, 将其next赋值为node
      current.next = newNode;
    }
    // 3.链表长度增加1
    this.length++;
  }
  // 链表指定位置添加节点 position位置是从0开始数
  Insert(position, value) {
    // 1.检测越界问题: 越界插入失败
    if (position < 0 || position > this.length) {
      return false;
    }
    // 2.定义变量, 保存新的节点,头节点,前一个节点,和当前位置
    let newNode = new Node(value);
    let current = this.head;
    let previous = null;
    let index = 0;
    // 3.判断是否列表是否在第一个位置插入
    if (position == 0) {
      this.head = newNode;
      newNode.next = current;
    } else {
      while (index < position) {
        // 保存当前节点
        previous = current;
        // 再读到下一个节点
        current = current.next;
        // 此时previous是current的前一个节点
        index++;
      }
      // 把新节点插入到previous和current中间
      previous.next = newNode;
      newNode.next = current;
    }
    // 4.length+1
    this.length++;
    return true;
  }
  // 链表内容输出
  ToString() {
    let current = this.head;
    let Stringfy = "";
    while (current) {
      Stringfy = Stringfy + "," + current.val;
      current = current.next;
    }
    // 去掉字符串中第一个逗号
    return Stringfy.slice(1);
  }
  // 根据位置移除节点
  RemoveAt(position) {
    // 1.检测越界问题: 越界移除失败, 返回false
    if (position < 0 || position >= this.length) {
      return false;
    }
    // 2.定义变量, 保存信息
    let current = this.head;
    let previous = null;
    let index = 0;
    // 3.判断是否是移除第一项
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;
    }
    // 4.length-1
    this.length--;
    // 5.返回移除的数据
    return current.value;
  }
  // 根据元素获取其在链表中的位置
  IndexOf(value) {
    // 1.定义变量, 保存信息
    let current = this.head;
    let index = 0;
    // 2.找到元素所在的位置
    while (current) {
      if (current.val === value) {
        return index;
      }
      index++;
      current = current.next;
    }
    // 3.来到这个位置, 说明没有找到, 则返回-1
    return -1;
  }
}

let ins = new LinkedListClass();
console.log("----------class方法实现----------");
ins.Append(1);
ins.Append(2);
ins.Append(3);
ins.Append(4);
console.log(ins.ToString());
console.log("-----------------");
ins.Insert(0, 9999);
console.log(ins.ToString());
console.log("-----------------");
ins.RemoveAt(2);
console.log(ins.ToString());
console.log("-----------------");
console.log(ins.IndexOf(4));
console.log("-----------------");
